package com.linzm.leetcode.primary.exercises4_20230129;

/**
 * @Author zimingl
 * @Date 2023/2/4 11:56
 * @Description: 二进制加法
 * 给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。
 * 输入为 非空 字符串且只包含数字 1 和 0。
 * 输入: a = "11", b = "10"
 * 输出: "101"
 * 每个字符串仅由字符 '0' 或 '1' 组成。
 * 1 <= a.length, b.length <= 10^4
 * 字符串如果不是 "0" ，就都不含前导零。
 */
public class Demo11 {
    public static void main(String[] args) {
        Demo11 demo11 = new Demo11();
        String a = "1010", b = "1011";
        String addBinary = demo11.addBinary2(a, b);
        System.out.println(addBinary);
    }

    private String addBinary(String a, String b) {
        int num1 = Integer.parseInt(a, 2);
        int num2 = Integer.parseInt(b, 2);
        int num = num1 + num2;
        return Integer.toString(num, 2);
    }

    private String addBinary2(String a, String b) {
        int n = a.length() - 1;
        int m = b.length() - 1;
        int carry = 0;
        StringBuilder  sb = new StringBuilder();
        while (n >= 0 || m >= 0 || carry != 0) {
            int sum = carry;
            if (n >= 0) {
                sum += a.charAt(n) - '0';
                n--;
            }
            if (m >= 0) {
                sum += b.charAt(m) - '0';
                m--;
            }
            sb.append(sum % 2);
            carry = sum / 2;
        }
        return sb.reverse().toString();
    }
}
